package com.example.leetcode.trainingcamp.week4.Thursday;

import java.util.HashMap;
import java.util.Map;

public class Offer08_01 {

    Map<Integer,Integer> map = new HashMap<>();

    int count = 1000000007;

    public int waysToStep(int n) {
        if (n ==1) return 1;
        if (n == 2) return 2;
        if (n == 3 ) return 4;
        if (map.containsKey(n)) return map.get(n);
        int result = ((waysToStep(n-1) + waysToStep(n-2)) % count + waysToStep(n-3)) % count;
        map.put(n,result);
        return result;
    }
}
